home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / gs24src.zip / GXFILL.C < prev    next >
C/C++ Source or Header  |  1992-03-05  |  24KB  |  732 lines
  1. /* Copyright (C) 1989, 1990, 1991 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* gxfill.c */
  21. /* Lower-level path filling procedures for GhostScript library */
  22. #include "gx.h"
  23. #include "gserrors.h"
  24. #include "gxfixed.h"
  25. #include "gxmatrix.h"
  26. #include "gxdevice.h"            /* for gx_color_index */
  27. #include "gzcolor.h"
  28. #include "gzpath.h"
  29. #include "gzstate.h"
  30. #include "gxcpath.h"
  31.  
  32. /* Import the fixed * fixed / fixed routine from gxdraw.c. */
  33. /* The second argument must be less than or equal to the third; */
  34. /* all must be non-negative, and the last must be non-zero. */
  35. extern fixed fixed_mult_quo(P3(fixed, fixed, fixed));
  36.  
  37. /* Define the structure for keeping track of active lines. */
  38. typedef struct active_line_s active_line;
  39. struct active_line_s {
  40.     gs_fixed_point start;        /* x,y where line starts */
  41.     gs_fixed_point end;        /* x,y where line ends */
  42. #define al_dx(alp) ((alp)->end.x - (alp)->start.x)
  43. #define al_dy(alp) ((alp)->end.y - (alp)->start.y)
  44.     fixed y_fast_max;        /* can do x_at_y in fixed point */
  45.                     /* if y <= y_fast_max */
  46. #define set_al_points(alp, startp, endp)\
  47.   (alp)->y_fast_max = max_fixed / (((endp).x > (startp).x ?\
  48.     (endp).x - (startp).x : (startp).x - (endp).x) | 1) + (startp).y,\
  49.   (alp)->start = startp, (alp)->end = endp
  50. #define al_x_at_y(alp, yv)\
  51.   ((yv) == (alp)->end.y ? (alp)->end.x :\
  52.    ((yv) <= (alp)->y_fast_max ?\
  53.     ((yv) - (alp)->start.y) * al_dx(alp) / al_dy(alp) :\
  54.     (stat(n_slow_x),\
  55.      fixed_mult_quo(al_dx(alp), (yv) - (alp)->start.y, al_dy(alp)))) +\
  56.    (alp)->start.x)
  57.     fixed x_current;        /* current x position */
  58.     fixed x_next;            /* x position at end of band */
  59.     segment *pseg;            /* endpoint of this line */
  60.     int direction;            /* direction of line segment */
  61. #define dir_up 1
  62. #define dir_down (-1)
  63. /* "Pending" lines (not reached in the Y ordering yet) use next and prev */
  64. /* to order lines by increasing starting Y.  "Active" lines (being scanned) */
  65. /* use next and prev to order lines by increasing current X, or if the */
  66. /* current Xs are equal, by increasing final X. */
  67.     active_line *prev, *next;
  68. /* Link together active_lines allocated individually */
  69.     active_line *alloc_next;
  70. };
  71.  
  72. /* Define the ordering criterion for active lines. */
  73. /* The xc argument is a copy of lp2->x_current. */
  74. #define x_precedes(lp1, lp2, xc)\
  75.   (lp1->x_current < xc || lp1->x_current == xc &&\
  76.    (lp1->start.x > lp2->start.x || lp1->end.x < lp2->end.x))
  77.  
  78. #ifdef DEBUG
  79. /* Internal procedures for printing active lines */
  80. private void
  81. print_active_line(char *label, active_line *alp)
  82. {    dprintf5("[f]%s %lx(%d): x_current=%f x_next=%f\n",
  83.              label, (ulong)alp, alp->direction,
  84.              fixed2float(alp->x_current), fixed2float(alp->x_next));
  85.     dprintf5("    start=(%f,%f) pt_end=%lx(%f,%f)\n",
  86.              fixed2float(alp->start.x), fixed2float(alp->start.y),
  87.              (ulong)alp->pseg,
  88.              fixed2float(alp->end.x), fixed2float(alp->end.y));
  89.     dprintf2("    prev=%lx next=%lx\n",
  90.          (ulong)alp->prev, (ulong)alp->next);
  91. }
  92. private void
  93. print_line_list(active_line *flp)
  94. {    active_line *lp;
  95.     for ( lp = flp; lp != 0; lp = lp->next )
  96.        {    fixed xc = lp->x_current, xn = lp->x_next;
  97.         dprintf3("[f]%lx(%d): x_current/next=%g",
  98.                  (ulong)lp, lp->direction,
  99.                  fixed2float(xc));
  100.         if ( xn != xc ) dprintf1("/%g", fixed2float(xn));
  101.         dputc('\n');
  102.        }
  103. }
  104. #define print_al(label,alp)\
  105.   if ( gs_debug['F'] ) print_active_line(label, alp)
  106. #else
  107. #define print_al(label,alp) 0
  108. #endif
  109.  
  110. /* Line list structure */
  111. struct line_list_s {
  112.     active_line *active_area;    /* allocated active_line list */
  113.     line_close_segment *close_area;    /* allocated closing line area */
  114.     uint close_count;
  115.     gs_fixed_rect box;        /* intersection of bounding boxes, */
  116.                     /* disregard lines outside this */
  117.     active_line *next_active;    /* next allocation slot */
  118.     active_line *limit;        /* limit of local allocation */
  119.     line_close_segment *next_line;    /* next line allocation slot */
  120.     active_line *y_list;        /* Y-sorted list of pending lines */
  121.     active_line *y_line;        /* most recently inserted line */
  122.     active_line x_head;        /* X-sorted list of active lines */
  123. #define x_list x_head.next
  124.         /* Put the arrays last so the scalars will have */
  125.         /* small displacements. */
  126.         /* Allocate a few active_lines and line_close_segments */
  127.         /* locally to avoid round trips through the allocator. */
  128. #define max_local_active 20
  129.     active_line local_active[max_local_active];
  130. #define max_local_close 5
  131.     line_close_segment local_close[max_local_close];
  132. };
  133. typedef struct line_list_s line_list;
  134. typedef line_list _ss *ll_ptr;
  135.  
  136. /* Forward declarations */
  137. private int alloc_line_list(P2(ll_ptr, uint));
  138. private void free_line_list(P1(ll_ptr));
  139. private int add_y_list(P2(gx_path *, ll_ptr));
  140. private int add_y_line(P4(segment *, segment *, int, ll_ptr));
  141. private int fill_loop(P5(gx_device_color *, int, ll_ptr,
  142.   gs_state *, fixed));
  143. private void insert_x_new(P2(active_line *, ll_ptr));
  144. private void update_x_list(P2(active_line *, fixed));
  145.  
  146. /* Statistics */
  147. #ifdef DEBUG
  148. #define stat(x) (x++)
  149. #define statn(x,n) (x += (n))
  150. private long n_fill;
  151. private long n_fill_alloc;
  152. private long n_y_up;
  153. private long n_y_down;
  154. private long n_x_step;
  155. private long n_slow_x;
  156. private long n_iter;
  157. private long n_find_y;
  158. private long n_band;
  159. private long n_band_step;
  160. private long n_band_fill;
  161. #else
  162. #define stat(x) 0
  163. #define statn(x,n) 0
  164. #endif
  165.  
  166. /* General area filling algorithm. */
  167. /* The adjust parameter is a hack for keeping small characters */
  168. /* from coming out too faint: it specifies an amount by which to expand */
  169. /* all sides of every filled region. */
  170. int
  171. gx_fill_path(gx_path *ppath, gx_device_color *pdevc, gs_state *pgs,
  172.   int rule, fixed adjust)
  173. {    gx_clip_path *pcpath = pgs->clip_path;
  174.     gs_fixed_rect cbox;
  175.     gx_path *pfpath;
  176.     gx_path ffpath;
  177.     int code;
  178.     line_list lst;
  179.     uint sub_count;
  180.     gx_device_clip cdev;
  181.     int do_clip;
  182.     /* Fatten everything a little to make it look better. */
  183.     /****** This is something of a hack. ******/
  184.     if ( adjust == 0 ) adjust = float2fixed(0.25);
  185.     /* Start by flattening the path.  We should do this on-the-fly.... */
  186.     if ( !ppath->curve_count )    /* don't need to flatten */
  187.         pfpath = ppath;
  188.     else
  189.        {    if ( (code = gx_path_flatten(ppath, &ffpath, pgs->flatness)) < 0 ) return code;
  190.         pfpath = &ffpath;
  191.        }
  192.     /* Check the bounding boxes. */
  193. #define ibox lst.box
  194.     gx_path_bbox(pfpath, &ibox);
  195.     gx_cpath_box_for_check(pcpath, &cbox);
  196.     if ( ibox.q.y <= cbox.q.y && ibox.q.x <= cbox.q.x &&
  197.          ibox.p.y >= cbox.p.y && ibox.p.x >= cbox.p.x
  198.        )
  199.        {    /* Path lies entirely within clipping rectangle */
  200.         do_clip = 0;
  201.        }
  202.     else
  203.        {    /* Intersect the path box and the clip bounding box. */
  204.         /* If the intersection is empty, this fill is a no-op. */
  205.         gs_fixed_rect bbox;
  206.         bbox = pcpath->path.bbox;
  207.         if ( ibox.p.x >= bbox.q.x || ibox.p.y >= bbox.q.y ||
  208.             ibox.q.x <= bbox.p.x || ibox.q.y <= bbox.p.y
  209.            )
  210.            {    /* Intersection of boxes is empty! */
  211.             code = 0;
  212.             goto skip;
  213.            }
  214.         do_clip = 1;
  215.        }
  216. #undef ibox
  217.     sub_count = pfpath->subpath_count;
  218.     if ( !(code = alloc_line_list(&lst, sub_count)) )
  219.        {    gx_device *save_dev;
  220.         if ( (code = add_y_list(pfpath, &lst)) < 0 )
  221.             goto nope;
  222.         if ( do_clip )
  223.            {    /* Set up a clipping device. */
  224.             gx_device *dev = (gx_device *)&cdev;
  225.             save_dev = gs_currentdevice(pgs);
  226.             cdev = gs_clip_device;
  227.             cdev.target = save_dev;
  228.             cdev.list = pcpath->list;
  229.             gx_set_device_only(pgs, dev);
  230.             (*dev->procs->open_device)(dev);
  231.            }
  232.         code = fill_loop(pdevc, rule, &lst, pgs, adjust);
  233.         if ( do_clip )
  234.             gx_set_device_only(pgs, save_dev);
  235. nope:        free_line_list(&lst);
  236.        }
  237. skip:    if ( pfpath != ppath )    /* had to flatten */
  238.         gx_path_release(pfpath);
  239. #ifdef DEBUG
  240. if ( gs_debug['f'] || gs_debug['F'] )
  241.        {    dputs("[f]calls alloc   up   down  step slowx  iter  find  band bstep bfill\n");
  242.         dprintf4("   %5ld %5ld %5ld %5ld",
  243.             n_fill, n_fill_alloc, n_y_up, n_y_down);
  244.         dprintf4(" %5ld %5ld %5ld %5ld",
  245.             n_x_step, n_slow_x, n_iter, n_find_y);
  246.         dprintf3(" %5ld %5ld %5ld\n",
  247.             n_band, n_band_step, n_band_fill);
  248.        }
  249. #endif
  250.     return code;
  251. }
  252.  
  253. /* Create a line list for a (flattened) path. */
  254. /* We pass in the list size, so that we can use this to iterate */
  255. /* over more than one path simultaneously (needed for clipping). */
  256. private int
  257. alloc_line_list(ll_ptr ll, uint sub_count)
  258. {    ll->active_area = 0;
  259.     ll->close_count = sub_count;
  260.     ll->close_area =
  261.       (sub_count <= max_local_close ?
  262.        ll->local_close :
  263.        (line_close_segment *)gs_malloc(sub_count, sizeof(line_close_segment),
  264.                        "closing lines"));
  265.     ll->next_line = ll->close_area;
  266.     if ( ll->close_area == 0 )
  267.         return_error(gs_error_VMerror);
  268.     ll->next_active = ll->local_active;
  269.     ll->limit = ll->next_active + max_local_active;
  270.     ll->y_list = 0;
  271.     ll->y_line = 0;
  272.     stat(n_fill);
  273.     return 0;
  274. }
  275.  
  276. /* Free the line list */
  277. private void
  278. free_line_list(ll_ptr ll)
  279. {    line_close_segment *lp;
  280.     active_line *alp;
  281.     /* Splice out any inserted closing lines */
  282.     for ( lp = ll->close_area; lp != ll->next_line; lp++ )
  283.        {    segment *prev = lp->prev, *next = lp->next;
  284.         prev->next = next;
  285.         if ( next ) next->prev = prev;
  286.         lp->sub->last = prev;
  287.        }
  288.     /* Free any individually allocated active_lines. */
  289.     while ( (alp = ll->active_area) != 0 )
  290.        {    active_line *next = alp->alloc_next;
  291.         gs_free((char *)alp, 1, sizeof(active_line),
  292.             "active line");
  293.         ll->active_area = next;
  294.        }
  295.     /* Free any separately allocated closing lines. */
  296.     if ( ll->close_area != ll->local_close && ll->close_area != 0 )
  297.        {    gs_free((char *)ll->close_area, ll->close_count,
  298.             sizeof(line_close_segment), "closing lines");
  299.        }
  300. }
  301.  
  302. /* Construct a Y-sorted list of lines for a (flattened) path. */
  303. /* We assume the path is non-empty.  Only include non-horizontal */
  304. /* lines where one endpoint is locally Y-minimal. */
  305. private int
  306. add_y_list(gx_path *ppath, ll_ptr ll)
  307. {    register segment *pseg = (segment *)ppath->first_subpath;
  308.     subpath *psub;
  309.     segment *plast;
  310.     int first_dir, prev_dir, dir;
  311.     segment *prev;
  312.     fixed xmin = ll->box.p.x, ymin = ll->box.p.y;
  313.     fixed xmax = ll->box.q.x, ymax = ll->box.q.y;
  314.     int code;
  315.     while ( pseg )
  316.        {    switch ( pseg->type )
  317.            {    /* No curves left */
  318.         case s_start:
  319.             psub = (subpath *)pseg;
  320.             plast = psub->last;
  321.             dir = 2;    /* hack to skip first line */
  322.             if ( plast->type != s_line_close )
  323.                {    /* Create a fake s_line_close */
  324.                 line_close_segment *lp = ll->next_line++;
  325.                 segment *next = plast->next;
  326.                 lp->next = next;
  327.                 lp->prev = plast;
  328.                 plast->next = (segment *)lp;
  329.                 if ( next ) next->prev = (segment *)lp;
  330.                 lp->type = s_line_close;
  331.                 lp->pt = psub->pt;
  332.                 lp->sub = psub;
  333.                 plast = (segment *)lp;
  334.                 psub->last = plast;
  335.                }
  336.             break;
  337.         default:        /* s_line, _close */
  338.            {    fixed iy = pseg->pt.y;
  339.             fixed py = prev->pt.y;
  340.             /* Lines falling entirely outside the ibox */
  341.             /* are treated as though they were horizontal, */
  342.             /* i.e., they are never put on the list. */
  343. #define compute_dir(xo, xe, yo, ye)\
  344.   (xo > xmax && xe > xmax ? 0 :\
  345.    ye > yo ? (ye <= ymin || yo >= ymax ? 0 : dir_up) :\
  346.    ye < yo ? (yo <= ymin || ye >= ymax ? 0 : dir_down) :\
  347.    0)
  348. #define add_dir_lines(prev2, prev, this, pdir, dir)\
  349.   if ( pdir )\
  350.    { if ( (code = add_y_line(prev2, prev, pdir, ll)) < 0 ) return code; }\
  351.   if ( dir )\
  352.    { if ( (code = add_y_line(prev, this, dir, ll)) < 0 ) return code; }
  353.             dir = compute_dir(prev->pt.x, pseg->pt.x, py, iy);
  354.             if ( dir > prev_dir )
  355.                {    add_dir_lines(prev->prev, prev, pseg, prev_dir, dir);
  356.                }
  357.             else if ( prev_dir == 2 )    /* first line */
  358.                 first_dir = dir;
  359.             if ( pseg == plast )
  360.                {    /* We skipped the first segment of the */
  361.                 /* subpath, so the last segment must */
  362.                 /* receive special consideration. */
  363.                 /* Note that we have `closed' all subpaths. */
  364.                 if ( first_dir > dir )
  365.                    {    add_dir_lines(prev, pseg, psub->next, dir, first_dir);
  366.                    }
  367.                }
  368.            }
  369. #undef compute_dir
  370. #undef add_dir_lines
  371.            }
  372.         prev = pseg;
  373.         prev_dir = dir;
  374.         pseg = pseg->next;
  375.        }
  376.     return 0;
  377. }
  378. /* Internal routine to test a line segment and add it to the */
  379. /* pending list if appropriate. */
  380. private int
  381. add_y_line(segment *prev_lp, segment *lp, int dir, ll_ptr ll)
  382. {    gs_fixed_point this, prev;
  383.     register active_line *alp = ll->next_active;
  384.     fixed y_start;
  385.     if ( alp == ll->limit )
  386.        {    /* Allocate separately */
  387.         alp = (active_line *)gs_malloc(1, sizeof(active_line), "active line");
  388.         if ( alp == 0 ) return_error(gs_error_VMerror);
  389.         alp->alloc_next = ll->active_area;
  390.         ll->active_area = alp;
  391.         stat(n_fill_alloc);
  392.        }
  393.     else
  394.         ll->next_active++;
  395.     this.x = lp->pt.x;
  396.     this.y = lp->pt.y;
  397.     prev.x = prev_lp->pt.x;
  398.     prev.y = prev_lp->pt.y;
  399.     if ( (alp->direction = dir) > 0 )
  400.        {    /* Upward line */
  401.         y_start = prev.y;
  402.         set_al_points(alp, prev, this);
  403.         alp->pseg = lp;
  404.        }
  405.     else
  406.        {    /* Downward line */
  407.         y_start = this.y;
  408.         set_al_points(alp, this, prev);
  409.         alp->pseg = prev_lp;
  410.        }
  411.     /* Insert the new line in the Y ordering */
  412.        {    register active_line *yp = ll->y_line;
  413.         register active_line *nyp;
  414.         if ( yp == 0 )
  415.            {    alp->next = alp->prev = 0;
  416.             ll->y_list = alp;
  417.            }
  418.         else if ( y_start >= yp->start.y )
  419.            {    /* Insert the new line after y_line */
  420.             while ( stat(n_y_up), (nyp = yp->next) != NULL && y_start > nyp->start.y )
  421.                 yp = nyp;
  422.             alp->next = nyp;
  423.             alp->prev = yp;
  424.             yp->next = alp;
  425.             if ( nyp ) nyp->prev = alp;
  426.            }
  427.         else
  428.            {    /* Insert the new line before y_line */
  429.             while ( stat(n_y_down), (nyp = yp->prev) != NULL && y_start < nyp->start.y )
  430.                 yp = nyp;
  431.             alp->prev = nyp;
  432.             alp->next = yp;
  433.             yp->prev = alp;
  434.             if ( nyp ) nyp->next = alp;
  435.             else ll->y_list = alp;
  436.            }
  437.        }
  438.     ll->y_line = alp;
  439.     print_al("add ", alp);
  440.     return 0;
  441. }
  442.  
  443. /* Main filling loop.  Takes lines off of y_list and adds them to */
  444. /* x_list as needed. */
  445. private int
  446. fill_loop(gx_device_color *pdevc, int rule, ll_ptr ll,
  447.   gs_state *pgs, fixed adjust)
  448. {    fixed adj2 = adjust << 1;
  449.     active_line *yll = ll->y_list;
  450.     gs_fixed_point pmax;
  451.     fixed y;
  452.     if ( yll == 0 ) return 0;        /* empty list */
  453.     pmax = ll->box.q;
  454.     y = yll->start.y;            /* first Y value */
  455.     ll->x_list = 0;
  456.     ll->x_head.x_current = min_fixed;    /* stop backward scan */
  457.     while ( 1 )
  458.        {    fixed y1, y0;
  459.         active_line *endp, *alp, *stopx;
  460.         fixed x;
  461.         int draw;
  462.         stat(n_iter);
  463.         /* Check whether we've reached the maximum y. */
  464.         if ( y >= pmax.y ) break;
  465.         /* Move newly active lines from y to x list. */
  466.         while ( yll != 0 && yll->start.y == y )
  467.            {    active_line *ynext = yll->next;    /* insert smashes next/prev links */
  468.             insert_x_new(yll, ll);
  469.             yll = ynext;
  470.            }
  471.         if ( ll->x_list == 0 )
  472.            {    /* No active lines, skip to next start */
  473.             if ( yll == 0 ) break;    /* no lines left */
  474.             y = yll->start.y;
  475.             continue;
  476.            }
  477.         /* Find the next evaluation point. */
  478.         /* Start by finding the smallest y value */
  479.         /* at which any currently active line ends */
  480.         /* (or the next to-be-active line begins). */
  481.         y1 = (yll != 0 ? yll->start.y : max_fixed);
  482.         for ( alp = ll->x_list; alp != 0; alp = alp->next )
  483.           if ( alp->end.y < y1 ) y1 = alp->end.y;
  484. #ifdef DEBUG
  485. if ( gs_debug['F'] )
  486.    {        dprintf2("[f]before loop: y=%f y1=%f:\n",
  487.                  fixed2float(y), fixed2float(y1));
  488.         print_line_list(ll->x_list);
  489.    }
  490. #endif
  491.         /* Now look for line intersections before y1. */
  492.         x = min_fixed;
  493.         y0 = y - adjust;
  494. #define have_pixels() (fixed_rounded(y0) < fixed_rounded(y1 + adjust))
  495.         draw = (have_pixels() ? 1 : -1);
  496.         /*
  497.          * Loop invariants:
  498.          *    alp = endp->next;
  499.          *    for all lines lp from stopx up to alp,
  500.          *      lp->x_next = al_x_at_y(lp, y1).
  501.          */
  502.         for ( alp = stopx = ll->x_list; stat(n_find_y), alp != 0;
  503.              endp = alp, alp = alp->next
  504.             )
  505.            {    fixed nx = al_x_at_y(alp, y1);
  506.             fixed dx_old, dx_den;
  507.             /* Check for intersecting lines. */
  508.             if ( nx >= x )
  509.                 x = nx;
  510.             else if
  511.                ( draw >= 0 && /* don't bother if no pixels */
  512.                  (dx_old = alp->x_current - endp->x_current) >= 0 &&
  513.                  (dx_den = dx_old + endp->x_next - nx) > dx_old
  514.                )
  515.                {    /* Make a good guess at the intersection */
  516.                 /* Y value using only local information. */
  517.                 fixed dy = y1 - y, y_new;
  518. #ifdef DEBUG
  519. if ( gs_debug['f'] || gs_debug['F'] )
  520.                 dprintf3("[f]cross: dy=%g, dx_old=%g, dx_new=%g\n",
  521.                   fixed2float(dy), fixed2float(dx_old),
  522.                   fixed2float(dx_den - dx_old));
  523. #endif
  524.                 /* Do the computation in single precision */
  525.                 /* if the values are small enough. */
  526.                 y_new =
  527.                   ((dy | dx_old) < 1L << (sizeof(fixed)*4-1) ?
  528.                    dy * dx_old / dx_den :
  529.                    fixed_mult_quo(dy, dx_old, dx_den))
  530.                   + y;
  531.                 /* The crossing value doesn't have to be */
  532.                 /* very accurate, but it does have to be */
  533.                 /* greater than y and less than y1. */
  534. #ifdef DEBUG
  535. if ( gs_debug['f'] || gs_debug['F'] )
  536.                 dprintf3("[f]cross y=%g, y_new=%g, y1=%g\n",
  537.                   fixed2float(y), fixed2float(y_new),
  538.                   fixed2float(y1));
  539. #endif
  540.                 stopx = alp;
  541.                 if ( y_new <= y ) y_new = y + 1;
  542.                 if ( y_new < y1 )
  543.                    {    y1 = y_new;
  544.                     nx = al_x_at_y(alp, y1);
  545.                     draw = 0;
  546.                    }
  547.                 if ( nx > x ) x = nx;
  548.                }
  549.             alp->x_next = nx;
  550.            }
  551.         /* Recompute next_x for lines before the intersection. */
  552.         for ( alp = ll->x_list; alp != stopx; alp = alp->next )
  553.             alp->x_next = al_x_at_y(alp, y1);
  554. #ifdef DEBUG
  555. if ( gs_debug['F'] )
  556.    {        dprintf1("[f]after loop: y1=%f\n", fixed2float(y1));
  557.         print_line_list(ll->x_list);
  558.    }
  559. #endif
  560.         /* Fill a multi-trapezoid band for the active lines. */
  561.         /* Don't bother if no pixel centers lie within the band. */
  562.         if ( draw > 0 || draw == 0 && have_pixels() )
  563.            {    active_line *alp = ll->x_list;
  564.             fixed height = y1 - y + adj2;
  565.             fixed xlbot, xltop;    /* as of last "outside" line */
  566.             int inside = 0;
  567.             stat(n_band);
  568.             x = min_fixed;
  569.             /* rule = -1 for winding number rule, i.e. */
  570.             /* we are inside if the winding number is non-zero; */
  571.             /* rule = 1 for even-odd rule, i.e. */
  572.             /* we are inside if the winding number is odd. */
  573.             /* Clever, eh? */
  574. #define inside_path_p() (inside & rule)
  575.             while ( alp != 0 )
  576.                {    fixed xbot = alp->x_current;
  577.                 fixed xtop = alp->x_next;
  578.                 print_al("step", alp);
  579.                 stat(n_band_step);
  580.                 if ( inside_path_p() )
  581.                  { inside += alp->direction;
  582.                    if ( !inside_path_p() )    /* about to go out */
  583.                     {    fixed wbot = xbot - xlbot + adj2;
  584.                     fixed wtop = xtop - xltop + adj2;
  585.                     int code;
  586.                     stat(n_band_fill);
  587.                     /* If lines are temporarily out of */
  588.                     /* order, wtop might be negative. */
  589.                     /* Patch this up now. */
  590.                     if ( wtop < 0 )
  591.                        {    xltop += wtop >> 1;
  592.                         wtop = 0;
  593.                        }
  594.                     code = gz_fill_trapezoid_fixed(
  595.                          xlbot - adjust,
  596.                          wbot, y0,
  597.                          xltop - adjust, wtop,
  598.                          height, 0, pdevc, pgs);
  599.                     if ( code < 0 ) return code;
  600.                     }
  601.                  }
  602.                 else            /* outside */
  603.                    {    inside += alp->direction;
  604.                     if ( inside_path_p() )    /* about to go in */
  605.                         xlbot = xbot, xltop = xtop;
  606.                    }
  607.                 alp = alp->next;
  608.                }
  609.            }
  610.         update_x_list(ll->x_list, y1);
  611.         y = y1;
  612.        }
  613.     return 0;
  614. }
  615.  
  616. /* Insert a newly active line in the X ordering. */
  617. private void
  618. insert_x_new(active_line *alp, ll_ptr ll)
  619. {    register active_line *next;
  620.     register active_line *prev = &ll->x_head;
  621.     register fixed x = alp->start.x;
  622.     alp->x_current = x;
  623.     while ( stat(n_x_step),
  624.         (next = prev->next) != 0 && x_precedes(next, alp, x)
  625.            )
  626.         prev = next;
  627.     alp->next = next;
  628.     alp->prev = prev;
  629.     if ( next != 0 ) next->prev = alp;
  630.     prev->next = alp;
  631. }
  632.  
  633. /* Clean up after a pass through the main loop. */
  634. /* If any lines are out of order, re-sort them now. */
  635. /* Also drop any ended lines. */
  636. private void
  637. update_x_list(active_line *x_first, fixed y1)
  638. {    fixed x;
  639.     register active_line *alp;
  640.     active_line *nlp;
  641.     for ( x = min_fixed, alp = x_first; alp != 0; alp = nlp )
  642.        {    fixed nx = alp->x_current = alp->x_next;
  643.         nlp = alp->next;
  644. #ifdef DEBUG
  645. if ( gs_debug['f'] || gs_debug['F'] )
  646.         dprintf4("[f]check %lx,x=%g %lx,x=%g\n",
  647.           (ulong)alp->prev, fixed2float(x),
  648.           (ulong)alp, fixed2float(nx));
  649. #endif
  650.         if ( alp->end.y == y1 )
  651.            {    /* Handle a line segment that just ended. */
  652.             segment *pseg = alp->pseg;
  653.             segment *next;
  654.             gs_fixed_point npt;
  655.             /*
  656.              * The computation of next relies on the fact that
  657.              * all subpaths have been closed.  When we cycle
  658.              * around to the other end of a subpath, we must be
  659.              * sure not to process the start/end point twice.
  660.              */
  661.             next =
  662.               (alp->direction == dir_up ?
  663.                (/* Upward line, go forward along path. */
  664.                 pseg->type == s_line_close ? /* end of subpath */
  665.                  ((line_close_segment *)pseg)->sub->next :
  666.                  pseg->next) :
  667.                (/* Downward line, go backward along path. */
  668.                 pseg->type == s_start ? /* start of subpath */
  669.                  ((subpath *)pseg)->last->prev :
  670.                  pseg->prev)
  671.               );
  672.             npt.y = next->pt.y;
  673. #ifdef DEBUG
  674. if ( gs_debug['F'] )
  675.             dprintf5("[f]ended %lx: pseg=%lx y=%f next=%lx npt.y=%f\n",
  676.                  (ulong)alp, (ulong)pseg, fixed2float(pseg->pt.y),
  677.                  (ulong)next, fixed2float(npt.y));
  678. #endif
  679.             if ( npt.y <= pseg->pt.y )
  680.                {    /* End of a line sequence */
  681.                 alp->prev->next = nlp;
  682.                 if ( nlp ) nlp->prev = alp->prev;
  683. #ifdef DEBUG
  684. if ( gs_debug['F'] )
  685.                 dprintf1("[f]drop %lx\n", (ulong)alp);
  686. #endif
  687.                 continue;
  688.                }
  689.             else
  690.                {    alp->pseg = next;
  691.                 npt.x = next->pt.x;
  692.                 set_al_points(alp, alp->end, npt);
  693.                 print_al("repl", alp);
  694.                }
  695.            }
  696.         if ( nx <= x )
  697.            {    /* Move alp backward in the list. */
  698.             active_line *prev = alp->prev;
  699.             active_line *next = nlp;
  700.             prev->next = next;
  701.             if ( next ) next->prev = prev;
  702.             while ( !x_precedes(prev, alp, nx) )
  703.                {
  704. #ifdef DEBUG
  705. if ( gs_debug['f'] || gs_debug['F'] )
  706.                 dprintf2("[f]swap %lx,%lx\n",
  707.                          (ulong)alp, (ulong)prev);
  708. #endif
  709.                 next = prev, prev = prev->prev;
  710.                }
  711.             alp->next = next;
  712.             alp->prev = prev;
  713.             /* next might be null, if alp was in */
  714.             /* the correct spot already. */
  715.             if ( next ) next->prev = alp;
  716.             prev->next = alp;
  717.            }
  718.         else
  719.             x = nx;
  720.        }
  721. #ifdef DEBUG
  722. if ( gs_debug['f'] || gs_debug['F'] )
  723.     for ( alp = x_first; alp != 0; alp = alp->next )
  724.      if ( alp->next != 0 && alp->next->x_current < alp->x_current )
  725.        {    lprintf("[f]Lines out of order!\n");
  726.         print_active_line("   1:", alp);
  727.         print_active_line("   2:", alp->next);
  728.         gs_exit(1);
  729.        }
  730. #endif
  731. }
  732.